#include <iostream>
#include <vector>
#include <memory>
#include <cstdlib>

using namespace std;

template<int inst>
class __default_alloc_template {
private:
    enum {
        __ALIGN = 8
    };  // 内存对齐大小
    enum {
        __MAX_BYTES = 128
    };  // 小对象的最大大小
    enum {
        __NFREELISTS = __MAX_BYTES / __ALIGN
    };  // 自由链表的数量

    static size_t ROUND_UP(size_t bytes) {
        return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
    }

    union obj {
        union obj *free_list_link;
        char client_data[1];
    };

    static obj *volatile free_list[__NFREELISTS];

    static size_t FREELIST_INDEX(size_t bytes) {
        return ((bytes + __ALIGN - 1) / __ALIGN - 1);
    }

    static void *refill(size_t n);

    static char *chunk_alloc(size_t size, int &nobjs);

    static char *start_free;
    static char *end_free;
    static size_t heap_size;

public:
    static void *allocate(size_t n);

    static void deallocate(void *p, size_t n);
};

template<int inst>
char *__default_alloc_template<inst>::start_free = nullptr;

template<int inst>
char *__default_alloc_template<inst>::end_free = nullptr;

template<int inst>
size_t __default_alloc_template<inst>::heap_size = 0;

template<int inst>
typename __default_alloc_template<inst>::obj *volatile
        __default_alloc_template<inst>::free_list[__NFREELISTS] = {nullptr};

template<int inst>
void *__default_alloc_template<inst>::allocate(size_t n) {
    obj *volatile *my_free_list;
    obj *result;

    if (n > (size_t) __MAX_BYTES) {
        return malloc(n);
    }

    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == nullptr) {
        void *r = refill(ROUND_UP(n));
        return r;
    }

    *my_free_list = result->free_list_link;
    return result;
}

template<int inst>
void __default_alloc_template<inst>::deallocate(void *p, size_t n) {
    obj *q = (obj *) p;
    obj *volatile *my_free_list;

    if (n > (size_t) __MAX_BYTES) {
        free(p);
        return;
    }

    my_free_list = free_list + FREELIST_INDEX(n);
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

template<int inst>
void *__default_alloc_template<inst>::refill(size_t n) {
    int nobjs = 20;
    char *chunk = chunk_alloc(n, nobjs);
    obj *volatile *my_free_list;
    obj *result;
    obj *current_obj;
    obj *next_obj;
    int i;

    if (1 == nobjs) return chunk;
    my_free_list = free_list + FREELIST_INDEX(n);

    result = (obj *) chunk;
    /* 挂链在这一步 */
    *my_free_list = next_obj = (obj *) (chunk + n);
    for (i = 1;; i++) {
        current_obj = next_obj;
        next_obj = (obj *) ((char *) next_obj + n);
        if (nobjs - 1 == i) {
            current_obj->free_list_link = 0;
            break;
        } else {
            current_obj->free_list_link = next_obj;
        }
    }
    return result;
}

template<int inst>
char *__default_alloc_template<inst>::chunk_alloc(size_t size, int &nobjs) {
    char *result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;

    if (bytes_left >= total_bytes) {
        result = start_free;
        start_free += total_bytes;
        return result;
    } else if (bytes_left >= size) {
        nobjs = (int) (bytes_left / size);
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return result;
    } else {
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        if (bytes_left > 0) {
            obj *volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *) start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj *) start_free;
        }
        start_free = (char *) malloc(bytes_to_get);
        if (start_free == nullptr) {
            int i;
            obj *volatile *my_free_list;
            obj *p;
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (p != nullptr) {
                    *my_free_list = p->free_list_link;
                    start_free = (char *) p;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);
                }
            }
            end_free = 0;
            start_free = (char *) malloc(bytes_to_get);  // 使用标准 malloc
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return chunk_alloc(size, nobjs);
    }
}


void test0(){
    using allocator = __default_alloc_template<0>;

    // 使用自定义二级配置器的 vector
    std::vector<int, std::allocator<int>> vec;

    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
    }

    for (const auto &elem: vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}


/**
 * 这里链表的原理是指针类型表示指针指向的范围
 * 比如申请了1024字节空间，但只有8B存了下一个节点的地址，剩余空间未使用，所以返回时初始位置有脏数据
 */
void test1(){
    union obj {
        union obj *free_list_link;
        char client_data[1];
    };
    obj* free_list[16] = {0};

    char* chunk1 = (char*)malloc(1024);
    char* chunk2 = (char*)malloc(1024);
    obj* result = (obj*)chunk1;
    result->free_list_link = (obj*)chunk2;
}

void test2(){
    // 使用自定义的二级配置器
    using allocator = __default_alloc_template<0>;
    allocator alloc;

    // 分配内存
    void* p1 = alloc.allocate(16);
    void* p2 = alloc.allocate(32);
    void* p3 = alloc.allocate(64);

    std::cout << "Allocated memory at: " << p1 << ", " << p2 << ", " << p3 << std::endl;

    // 使用分配的内存（例如，可以将其转换为特定类型并使用）
    int* int_ptr = static_cast<int*>(p1);
    for (int i = 0; i < 4; ++i) {
        int_ptr[i] = i * 10;
        std::cout << int_ptr[i] << " ";
    }
    std::cout << std::endl;

    // 释放内存
    alloc.deallocate(p1, 16);
    alloc.deallocate(p2, 32);
    alloc.deallocate(p3, 64);

}




//__default_alloc_template<0> alloc;
int main() {
    test2();

    return 0;
}



